package com.zjsru.oneDay;

import java.util.ArrayList;
import java.util.List;

/**
 * 和为 K 的最少斐波那契数字数目
 * <p>
 * <p>
 * 输入：k = 7
 * 输出：2
 * 解释：斐波那契数字为：1，1，2，3，5，8，13，……
 * 对于 k = 7 ，我们可以得到 2 + 5 = 7 。
 * <p>
 * 输入：k = 19
 * 输出：3
 * 解释：对于 k = 19 ，我们可以得到 1 + 5 + 13 = 19 。
 */
public class findMinFibonacciNumbers {
    static List<Integer> list = new ArrayList<>();

    static {
        list.add(1);
        int a = 1, b = 1;
        while (b <= (int) 1e9) {
            int c = a + b;
            a = b;
            b = c;
            list.add(c);
        }
    }

    public int findMinFibonacciNumbers(int k) {
        int ans = 0;
        while (k != 0) {
            int l = 0, r = list.size() - 1;
            while (l < r) {
                int mid = l + r + 1 >> 1;
                if (list.get(mid) <= k) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            k -= list.get(r);
            ans++;
        }
        return ans;
    }

    public static void main(String[] args) {
        findMinFibonacciNumbers findMinFibonacciNumbers = new findMinFibonacciNumbers();
        int k = 7;
        System.out.println(findMinFibonacciNumbers.findMinFibonacciNumbers(k));
    }
}
